package com.honeywen.mymvc.leetcode;

/**
 * 234. 回文链表
 * https://leetcode-cn.com/problems/palindrome-linked-list/
 * @author wangwei
 * @date 2019/2/20 下午3:17
 */
public class HuiwenListTest {

    private static ListNode node = null;
    private static ListNode nn = null;

    static {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        node = node1;

        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(2);
        ListNode n5 = new ListNode(1);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        nn = n1;
    }

    private static void print(ListNode head) {
        while (head != null) {
            System.out.print(head.val + "->");
            head = head.next;
        }
        System.out.println();

    }

    public static void main(String[] args) {
//        print(node);
//        System.out.println(isPalindrome(node));
        print(nn);
        System.out.println(isPalindrome(nn));

    }

    public static boolean isPalindrome(ListNode head) {

        // 1. 取得中点
        // 2. 截取，翻转
        // 3. 比较

        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode second = reverse(slow);
        while (second != null) {
            if (second.val != head.val) {
                return false;
            }
            second = second.next;
            head = head.next;
        }

        return true;

    }


    // 先学会翻转链表，

    public static ListNode reverse(ListNode head) {

        ListNode prev = null;
        ListNode curr = head;
        ListNode next = null;


        while (curr != null) {
            // 1.保存 curr.next,
            // 2.将curr.next 指向 prev
            // 3. curr 翻转到curr.next,prev前进

            next = curr.next;
            curr.next = prev;

            prev = curr;
            curr = next;

        }
        // 循环结束
        curr = prev;

        return curr;

    }

    public static ListNode reverse2(ListNode head) {

        if (head != null && head.next == null) {
            return head;
        }


        ListNode prev = head;
        ListNode curr = head.next;
        ListNode next = head.next.next;

        curr.next = prev;

        prev = curr;
        curr = next;


        return null;









    }




}
